/**
 * @param {number} n
 * @return {number}
 */
export var fib = function (n) {
  if (n < 2) return n
  return fib(n - 1) + fib(n - 2)
}

/**
 * @param {number} n
 * @return {number}
 */
export var fib2 = function (n) {
  return dfs(n, {})
}

function dfs(n, memo) {
  if (n < 2) return n
  if (memo[n]) return memo[n]
  memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo)
  return memo[n]
}

/**
 * @param {number} n
 * @return {number}
 */
export var fib3 = function (n) {
  if (n < 2) return n
  let a = 0
  let b = 1
  for (let i = 2; i <= n; i++) {
    const c = a + b
    a = b
    b = c
  }
  return b
}
